Until recently, most text on raster displays used characters represented as binary matrices, with ones and zeros corresponding to the black and white dots to be displayed. Typically, only one set of characters was provided, simple and tuned to the characteristics of the display.
While bi-level matrix representations of characters work quite well when high-resolution characters and display devices are available, at low resolutions--such as on computer terminals and low cost laser printers--the one-bit characters do not accurately resemble their analog predecessors. FIG. 1 shows how two characters from the Latin 725 Medium font look when printed using a low resolution bi-level font, and when using a grayscale font at the same resolution. As shown in FIG. 1, grayscale devices can increase the effective resolution of a character with a fixed number of pixels by using gray pixels in the representation of a character, as well as black and white ones. Note that for the purposes of this specification, the term "display" refers both to monitor type display devices, and to printers.
The terms "bi-level" and "bi-modal" are used synonymously with the term "black and white" for describing displays and images defined by pixels which are either on or off (i.e., white or black). For the purposes of this description, white pixels form the background, while black pixels form characters.
The term "master character font" refers to any high resolution, bi-level character font which can be used as the basis for generating a "grayscale character font", which is a lower resolution character font in which each pixel is defined using a "grayscale" having a multiplicity (i.e., more than two) of available values.
The terms "summed area filter", "summed area table", "summed area filter array", and "summed area array" are used interchangeably herein, except where otherwise indicated.
Using the present invention, master character fonts are decomposed into rectangles, and each individual rectangle is efficiently convolved with a summed area representation of a filter to construct the grayscale character.
The use of grayscale fonts is based on the principle that, as objects become too small to resolve spatially, size and intensity become interchangeable. One of the principle functions carried out by the human visual system is to find edges in the scene being viewed. When objects are too small to resolve spatially--such as a pixel from a sufficient viewing distance--the gray intensity of that object may be "misinterpreted" as spatial components of light and dark; i.e., an "edge" will be inferred where there really is an area of uniform illumination. It is this perceptual effect which is exploited in the use of grayscale.
Note that grayscale pixels provide no information about the orientation of the inferred edge; that information is deduced by the visual system based on the intensities of the surrounding pixels. For example, assuming for the moment that only the immediately adjacent pixels will influence the perception of a selected grayscale pixel, if the pixels to the left are black, the pixels to the right are white, and those above and below are the same gray as the selected pixel, a vertical edge will be perceived with a sub-pixel position (i.e., at a position between standard pixel grid points) depending on the intensity of the gray pixels. On the other hand, if the pixels above are white, the pixels below are black, and the pixels to the left and right are gray, a horizontal edge will be perceived with a sub-pixel position again depending on the intensity of the gray pixels.
Notice, therefore, that the same value of gray in a selected pixel will at one time be interpreted as resolution in the hoizontal direction and at another time in the vertical direction (or even some other orientation, depending on the surrounding pixels). In other words, once orientation information of the perceived edge is resolved with respect to the surrounding pixels, the grayscale is utilized as resolution information. Therefore, to a first approximation, the added number of grayscale levels (not the added number of bits) is advantageously exploited regardless of the orientation of the edge; it merely serves to position the edge more precisely.
For many applications (such as text entry), it will be sufficient to provide a single version of a grayscale font for each size and style which is needed on a particular display device. However, since grayscale can be used to achieve sub-pixel positioning of edges, one could generate many grayscale versions of the same font at a particular size and for a specific device, each differing only slightly from the next in terms of the sub-pixel position of the character's edges. By using the particular grayscale version which best approximates each character's specified sub-pixel position, one could reduce the spacing error that would otherwise result from positioning characters on whole pixel boundaries.
The standard method of generating grayscale fonts in the prior art is to filter bi-level master character fonts. Unfortunately, most of the previously known, efficient filtering techniques cannot directly be applied. For example, prefiltering is impractical, due to the number of character masters and the requirement of sub-pixel positioning.
The present invention concerns a fast filtering technique especially adapted to the task of producing grayscale fonts from high resolution bi-level master fonts. An important feature of the present invention is that it is so efficient that filtering characters for grayscale displays is feasible in realtime on personal computers and personal workstations.
Although grayscale text has gotten some limited commercial exposure lately (e.g., IBM's Yoda terminal and Bitstream Inc.'s grayscale fonts), two factors have combined to restrict its usage mainly to specialized environments such as paint programs and slide preparation packages, where the grayscale value is used as a weight for interpolating between the text color and a variegated background.
First, the techniques previously discussed in the literature are computationally expensive, and second, there has been little quality control over the resultant fonts. Furthermore, a model of each device must be incorporated into the font generation system because the generation of gray pixels depends on the characteristics of the display device, including pixel size, pixel shape (point spread function), overlap, intensity gamma, and spatial inhomogeneities. Otherwise, good-looking fonts produced for one monitor may not perform well on another. See Kajiya, J. and M. Ullner, "Filtering High Quality Text for Display on Raster Scan Devices," Computer Graphics, Volume 15, Number 3, SIGGRAPH 1981 Proceedings (August 1981) pp. 7-15.
Therefore a primary object of the present invention is to provide a font production tool which is efficient and filter independent. With appropriate parametrization of a display device's characteristics in the form of an appropriate filter or set of filters, the invention will efficiently produce device dependent grayscale fonts from a master font library.
As will be described below, the present invention can efficiently produce numerous fonts at numerous sizes, for various devices, and can use different filters for different applications. In order for this task to be feasible, fonts must be producible at rates far greater than have heretofore been reported. The detailed description shows how, by meeting a few reasonable assumptions, one can drastically reduce the computational expense of generating grayscale fonts for both experimentation purposes, and more generally for font production.